package org.adhibition;

import org.linearlist.LinkList;
import org.linearlist.Node;

/**
 * @author: 默苍璃
 * @date: 2023-04-10 10:56
 * <p>
 * 将两个有序链表La和Lb合并为一个有序链表
 */
public class Chap2_2 {
    public static <T extends Comparable> void MergeList_L(LinkList<T> La, LinkList<T> Lb, LinkList<T> Lc)
        /*已知单链表La和Lb的元素按值非递减排列。归并La和Lb得到新的单链表Lc，        Lc的元素也按值非递减排列*/ {
        Node<T> pa, pb, pc;
        pa = La.getHead().next;
        pb = Lb.getHead().next;
        pc = Lc.getHead();
        while (pa != null && pb != null) {
            //pa在前
            if (pa.data.compareTo(pb.data) <= 0) {
                pc.next = pa;
                pc = pa;
                pa = pa.next;
            } else {
                pc.next = pb;
                pc = pb;
                pb = pb.next;
            }
        }
        while (pa != null) {
            pc.next = pa;
            pc = pa;
            pa = pa.next;
        }
        while (pb != null) {
            pc.next = pb;
            pc = pb;
            pb = pb.next;
        }
        La.clear();
        Lb.clear();
    }


    public static void main(String[] args) {
        int i, j, k = 0;
        int[] a = {12, 23, 35, 49, 56};
        int[] b = {10, 15, 20};
        LinkList<Integer> La = new LinkList<>();
        LinkList<Integer> Lb = new LinkList<>();
        LinkList<Integer> Lc = new LinkList<>();
        for (i = 0; i < a.length; i++) {
            //将数组中各元素插入到单链表中
            La.add(a[i], i + 1);
        }
        System.out.println("单链表a中的数据元素为：");
        La.nextOrder();

        for (j = 0; j < b.length; j++) {
            //将数组中各元素插入到单链表中
            Lb.add(b[j], j + 1);
        }
        System.out.println("单链表b中的数据元素为：");
        Lb.nextOrder();

        MergeList_L(La, Lb, Lc);
        System.out.println("单链表C中的数据元素为：");
        Lc.nextOrder();

        //lc长度始终为0
        System.out.println(Lc.size());
    }

}